package com.fe.class05;

import java.util.Arrays;

/**
 * @Description 递归方式实现快排-V1.0
 * @Author sosuke :-)
 * @Date 2021/12/25 22:16
 */
public class Code03_QuickSortRecursive {

    public static void quickSort(int[] arr) {
        if (null == arr || arr.length < 2) return;
        // System.out.println("arr="+Arrays.toString(arr));
        process01(arr, 0, arr.length - 1);
        // System.out.println("最终arr="+Arrays.toString(arr));
        // System.out.println();
    }

    // 如果数组本来就有序，则每次partition的效果都最差，等差数列，则时间复杂度为O(n^2)
    private static void process01(int[] arr, int L, int R) {
        if (L >= R) return;
        // 以arr[R]为划分值将arr划分成小于、等于、大于划分值的三部分
        int privot = netherLandsFlag01(arr, L, R);
        // System.out.println("L="+L+", R="+R+", netherLands="+ Arrays.toString(arr)+", privot="+privot);
        process01(arr, L, privot - 1); // 递归划分小于等于区域
        process01(arr, privot + 1, R); // 递归划分大于区域
    }

    /**
     * 荷兰国旗问题，以arr[R]作为划分值，将arr划分成两部分
     * 先把arr[R]剔除，相当于在arr[L...R-1]中以arr[R]为标准划分为两部分
     *
     * @param arr
     * @param L
     * @param R
     * @return 左边界（最终arr[R]在左边界位置）
     */
    private static int netherLandsFlag01(int[] arr, int L, int R) {
        if (L > R) return -1;
        if (L == R) return L;
        // 设计两个窗口位置分别表示<arr[R]和>arr[R]
        int windowL = L - 1; //<=arr[R]区域的右边界
        int curIndex = L;
        while (curIndex < R) { // 当前位置不能和>arr[R]区域的左边界撞上
            if (arr[curIndex] <= arr[R]) {
                swap(arr, curIndex, ++windowL);
            }
            curIndex++;
        }
        // 最后将arr[R]加入进arr[L...R-1]中来
        swap(arr, ++windowL, R);
        return windowL;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int testTime = 5000; // 测试次数
        int maxSize = 100; // 数组数据个数
        int maxValue = 200; // 数组中最大值
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            quickSort(arr1);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                System.out.println("Fuck");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                return;
            }
        }
        System.out.println("Nice!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // [-? , +?]
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

}
